<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            完全背包爬楼梯
            题目描述: 
                给你一组硬币数，表示不同面额的硬币；以及一个整数amount，表示总金额；
                计算并返回可以凑成总金额所需的最少硬币个数
            示例 1：

            输入：coins = [1, 2, 5], amount = 11
            输出：3 
            解释：11 = 5 + 5 + 1

            示例 2：

            输入：coins = [2], amount = 3
            输出：-1
            示例 3：

            输入：coins = [1], amount = 0
            输出：0
        */


        /*
            动态规划解法:
            类型：完全背包；
            递推公式：Math.min(dp[j], dp[j - coins[i]] + 1),
            遍历顺序：外层是物品或者外层是背包，都没有关系；但是背包必须是正序，因为是完全背包
        */


        /* 
            O(m * n)
            O(n)
        */
        var coinChange = function(coins, amount) {
            let dp = new Array(amount + 1).fill(0)
            for (let j = 1; j <= amount; j++) {
                // 用Infinity而不是min的值，为什么呢？因为有可能[0, 1] 1这个测试用例不通过
                dp[j] = Infinity
            }
            for (let i = 0; i < coins.length; i++) {
                for (let j = 1; j <= amount; j++) {
                    if (j - coins[i] >= 0) {
                        dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1)
                    }
                }
            }
            console.log(dp, 'dp');
            /* 
            如果最后一个值等于最大的硬币数，说明没有凑齐，就返回-1；比如 [2] 3这个例子，最大硬币就是2，dp[amount] 初始化时最大就是2，如果amount能被2凑齐，dp的最后一个数不能还是2，否则就是Math.min(dp[j], dp[j - coins[i]] + 1) 后面这个dp[j - coins[i]] + 1 没有生效，
            
             dp[3] = Math.min(dp[3], dp[1] + 1) = Math.min(2, dp[1] + 1) 后面这个凑数没有生效
            */
            return dp[amount] === Infinity ? -1 : dp[amount]
        };
        // console.log(coinChange([1, 2, 5], 11));
        // console.time('100');
        // console.log(coinChange([1, 1, 1], 1111));
        // console.timeEnd('100');
        // console.log(coinChange([2], 3));
        console.log(coinChange([1], 1));
        // console.log(coinChange([1], 0));
    </script>
</body>

</html>